Ông là người thôn Đông Thành, xã Tịnh Thọ, huyện Sơn Tịnh, tỉnh Quảng Ngãi. Cha là ông Nguyễn Tấn Trực.

Gia nhập quân chúa Nguyễn

Năm 1768, ông gia nhập quân chúa Nguyễn.

Ngày rằm tháng Giêng năm Quý Tỵ (1773), Nguyễn Tăng Long cầm một đội kỵ bịnh tràn xuống đánh chiếm huyện lỵ Bình Sơn, rồi ngán ngữ ranh giới phủ Hòa Nghĩa (giữa Quảng Nam và Thừa Tuyên).

Cũng trong năm đó, quân Tây Sơn đánh hạ được thành Quy Nhơn, kiểm soát được các vùng đất từ Quảng Ngãi đến Bình Thuận. Nguyễn Tăng Long đến gia nhập quân Tây Sơn. Là người có công xây dựng phủ Quảng Nghĩa, là căn cứ Tây Sơn tả đạo, góp phần thiết lập triều đại Tây Sơn.

Trở thành tướng Tây Sơn

Kể từ năm 1776 đến năm 1783, quân Tây Sơn liên tục tấn công quân của chúa Nguyễn ở Gia Định. Trong thời gian này Nguyễn Tăng Long lập nhiều chiến công nên được phong làm Đô đốc Kỵ binh.

Từ năm 1784-1785, ông theo tướng Nguyễn Huệ lập chiến công tại trận Rạch Gầm-Xoài Mút.

Năm 1786, ông cùng Bắc Bình Vương Nguyễn Huệ tiến quân ra Bắc. Sau khi chúa Trịnh bị đánh đổ, ông được thăng chức làm Đại Đô Đốc trấn thủ Nghệ An.

Năm Kỷ Dậu (1789), ông lại cùng vua Quang Trung (tức Nguyễn Huệ) ra Bắc, và đã đánh tan hơn 20 vạn quân nhà Thanh. Lập công, Nguyễn Tăng Long được phong tước Nghĩa Đức hầu.

Nguyễn Tăng Long có sắc phong của vua Cảnh Thịnh (nhà Tây Sơn) ban chức đô đốc, ở quê thường gọi là "Đô Miên".

Triều Cảnh Thịnh phong cho ông chức Tả Võ lâm quân,đại tướng quân.